// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem354.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=354 lang=cpp
 *
 * [354] 俄罗斯套娃信封问题
 */

// @lc code=start
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b) {
            if (a[0] == b[0]) return a[1] >= b[1];
            return a[0] < b[0];
        });

        int n = envelopes.size();
        vector<int> dp(n + 1, 0);
        int len = 1;
        dp[len] = envelopes[0][1];
        for (int i = 1; i < n; ++i) {
            if (envelopes[i][1] > dp[len]) {
                dp[++len] = envelopes[i][1];
            } else {
                int left = 1, right = len, pos = 0;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (dp[mid] >= envelopes[i][1]) {
                        right = mid - 1;
                    } else {
                        pos = mid;
                        left = mid + 1;
                    }
                }
                dp[pos + 1] = envelopes[i][1];
            }
        }
        return len;
    }
};
// @lc code=end

